import collections


class DoublyLinkedList:
    """双端链表"""

    class _Node:
        __slots__ = "val", "prev", "next"

        def __init__(self, val, prev, next):
            self.val = val
            self.prev = prev
            self.next = next

    def __init__(self):
        self._header = self._Node(None, None, None)
        self._trailer = self._Node(None, None, None)
        self._header.next = self._trailer
        self._trailer.prev = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def __bool__(self):
        return self._size > 0

    def first(self):
        if not self:
            raise KeyError("empty deque")
        return self._header.next

    def last(self):
        if not self:
            raise KeyError("empty deque")
        return self._trailer.prev

    def _insert_between(self, val, before, after):
        newest = self._Node(val, before, after)
        before.next = newest
        after.prev = newest
        self._size += 1
        return newest

    def delete_node(self, node):
        before = node.prev
        after = node.next
        before.next = after
        after.prev = before
        self._size -= 1
        return node

    def insert_first(self, val):
        return self._insert_between(val, self._header, self._header.next)

    def insert_last(self, val):
        return self._insert_between(val, self._trailer.prev, self._trailer)

    def delete_first(self):
        if not self:
            raise KeyError("empty deque")
        return self.delete_node(self._header.next)

    def delete_last(self):
        if not self:
            raise KeyError("empty deque")
        return self.delete_node(self._trailer.prev)

    def __repr__(self):
        ans = []
        node = self._header.next
        while node.next:
            ans.append(str(node.val))
            node = node.next
        return "deque:" + "<->".join(ans)


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0

        # 频数对应双端链表：node.val = [key,value,freq]
        self.freq = collections.defaultdict(DoublyLinkedList)

        # key对应双端链表结点
        self.cache = {}

        # 最小频数
        self.min_freq = 0

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._increase(node)
            return node.val[1]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val[1] = value
            self._increase(node)
        else:
            if 0 < self.size == self.capacity:
                self._delete()
                self.size -= 1

            if self.size < self.capacity:
                node = self.freq[1].insert_first([key, value, 1])
                self.cache[key] = node
                self.size += 1

            if self.size == self.capacity:
                self.min_freq = 1

    def _increase(self, node):
        """增加指定结点的频数"""
        f = node.val[2]
        node.val[2] += 1
        self.freq[f].delete_node(node)
        node = self.freq[f + 1].insert_first(node.val)
        self.cache[node.val[0]] = node

        if not self.freq[f]:
            self.freq.pop(f)
            if self.min_freq == f:
                self.min_freq += 1

    def _delete(self):
        """移除最低频的结点"""
        node = self.freq[self.min_freq].delete_last()
        self.cache.pop(node.val[0])


if __name__ == "__main__":
    obj = LFUCache(2)
    obj.put(1, 1)
    obj.put(2, 2)
    print(obj.get(1))  # 1
    obj.put(3, 3)
    print(obj.get(2))  # -1
    print(obj.get(3))  # 3
    obj.put(4, 4)
    print(obj.get(1))  # -1
    print(obj.get(3))  # 3
    print(obj.get(4))  # 4
    print()

    # 测试用例4
    obj = LFUCache(0)
    obj.put(0, 0)
    print(obj.get(0))  # -1
